/*
给定一个单链表的头节点  head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。

类似于有序数组转平衡二叉树，只不过我们需要找到有序链表的中间节点。
*/

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    // 使用快慢指针找中间节点
    ListNode* getMid(ListNode* left, ListNode* right) {
        if (left == nullptr) {
            return nullptr;
        }

        ListNode* slow = left;
        ListNode* fast = left;

        // 可以简单画一下，找到退出条件
        // n1->n2->n3->n4
        // n1->n2->n3

        while (fast != right && fast->next != right) {
            fast = fast->next;
            fast = fast->next;
            slow = slow->next;
        }

        return slow;
    }

    // 因为我们无法一步定位链表尾节点，可以使用nullptr表示尾节点
    // [left, right)
    TreeNode* helper(ListNode* left, ListNode* right) {
        if (left == right) {
            return nullptr;
        }

        ListNode* mid = getMid(left, right);

        TreeNode* root = new TreeNode(mid->val);
        root->left = helper(left, mid);
        root->right = helper(mid->next, right);

        return root;
    }

    TreeNode* sortedListToBST(ListNode* head) {
        return helper(head, nullptr);
    }
};

int main() {
    return 0;
}